package kyssion.leetcode.num51_100;

public class code52_N皇后2 {

    public static void main(String[] args) {
        System.out.println(new code52_N皇后2().totalNQueens(4));
    }

    int num;

    public int totalNQueens(int n) {
        char[][] item = new char[n][n];
        init(item);
        boolean[] col = new boolean[n];
        boolean[] row = new boolean[n];
        boolean[] leftDiag = new boolean[2*n];
        boolean[] rightDiag = new boolean[2*n];
        num=0;
        ans(n, 0, item, col, row, leftDiag, rightDiag);
        return num;
    }

    public void init(char[][] item) {
        for (int a = 0; a < item.length; a++) {
            for (int b = 0; b < item[a].length; b++) {
                item[a][b] = '.';
            }
        }
    }

    public void ans(int n, int indexLine, char[][] item,
                    boolean[] col, boolean[] row, boolean[] leftDiga, boolean[] rightDiag) {
        if (indexLine >= n) {
            num++;
        }
        for (int a = 0; a < n; a++) {
            if (!col[a] && !row[a] && !leftDiga[n-a+indexLine] && !rightDiag[a+indexLine]) {
                col[a] = row[a] = leftDiga[n-a+indexLine] = rightDiag[a+indexLine] = true;
                item[indexLine][a] = 'Q';
                ans(n, indexLine + 1, item, col, row, leftDiga, rightDiag);
                item[indexLine][a] = '.';
                col[a] = row[a] = leftDiga[n-a+indexLine] = rightDiag[a+indexLine] = false;
            }
        }
    }
}
